// step 0# 全局变量定义
int *path;         // 临时路径数组
int **ans;         // 结果二维数组
int *used;         // 元素是否被使用的标记数组
int pathTop, ansTop;  // 当前路径长度和结果数量

// step 1# 拷贝当前 path 到结果 ans 中
void copyPath() {
    int *tempPath = (int*)malloc(sizeof(int) * pathTop);
    for(int i = 0; i < pathTop; ++i) {
        tempPath[i] = path[i];
    }
    ans[ansTop++] = tempPath;
}

// step 2# 回溯主函数：用于构建所有不重复的排列
void backTracking(int* used, int *nums, int numsSize) {
    // step 2.1# 如果路径长度等于原数组长度，说明构造出一个完整排列
    if(pathTop == numsSize) {
        copyPath();
        return;
    }

    for(int i = 0; i < numsSize; i++) {
        // note 1### 
        // step 2.2# 剪枝条件：
        // a. 当前元素已经用过，不能重复使用
        // b. 当前元素与前一个值相同，且前一个没被使用（同一树层跳过重复）
        if(used[i] || (i > 0 && nums[i] == nums[i-1] && used[i-1] == 0))
            continue;

        // step 2.3# 选择当前元素
        used[i] = 1;
        path[pathTop++] = nums[i];

        // step 2.4# 递归进入下一层
        backTracking(used, nums, numsSize);

        // step 2.5# 回溯，撤销选择
        used[i] = 0;
        --pathTop;
    }
}

// step 3# 排序用的比较函数，用于去重前的预处理
int cmp(void* elem1, void* elem2) {
    return *((int*)elem1) - *((int*)elem2);
}

// step 4# 主函数入口：生成所有不重复的全排列
int** permuteUnique(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    // step 4.1# 排序，为了处理重复元素
    qsort(nums, numsSize, sizeof(int), cmp);

    // step 4.2# 初始化全局变量和辅助数组
    pathTop = ansTop = 0;
    path = (int*)malloc(sizeof(int) * numsSize);
    ans = (int**)malloc(sizeof(int*) * 1000);
    used = (int*)malloc(sizeof(int) * numsSize);
    for(int i = 0; i < numsSize; i++) {
        used[i] = 0;
    }

    // step 4.3# 启动回溯
    backTracking(used, nums, numsSize);

    // step 4.4# 设置返回结果
    *returnSize = ansTop;
    *returnColumnSizes = (int*)malloc(sizeof(int) * ansTop);
    for(int z = 0; z < ansTop; z++) {
        (*returnColumnSizes)[z] = numsSize;
    }

    // step 4.5# 返回结果指针
    return ans;
}
